package com.acyouzi.leetcode.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 17/9/6 14:52
 *
 * @author sunxu
 */
class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}
// https://leetcode.com/problems/non-overlapping-intervals/description/
public class NonOverlapping {
  // 开始要查找重叠区间，判断方法是看如果前一个区间的end大于后一个区间的start，
  // 那么一定是重复区间，此时我们结果res自增1，我们需要删除一个，
  // 那么此时我们究竟该删哪一个呢，为了保证我们总体去掉的区间数最小，我们去掉那个end值较大的区间
  public int eraseOverlapIntervals(Interval[] intervals) {
    int res = 0;
    int end = Integer.MIN_VALUE;
    Arrays.sort(intervals, new Comparator<Interval>() {
      public int compare(Interval o1, Interval o2) {
        return o1.end - o2.end;
      }
    });
    for (Interval interval : intervals){
      if (end > interval.start){
        res ++;
        end = Math.min(end,interval.end);
      }else{
        end = interval.end;
      }
    }
    return res;
  }
}
